package day20210620;

import treenode.SimpleTreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 94. 二叉树的中序遍历
 * 其核心思想如下：
 *
 * 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
 * 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
 * 如果遇到的节点为灰色，则将节点的值输出。
 *
 * 作者：hzhu212
 * 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 *          1
 *              2
 *           3
 * @author lizy
 * @date 2021/06/20
 */
class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 1;
        simpleTreeNode.right = new SimpleTreeNode(2);
        simpleTreeNode.right.left = new SimpleTreeNode(3);
        System.out.println(solution.inorderTraversal(simpleTreeNode));
    }

    class ColorNode {
        SimpleTreeNode node;
        String color;

        public ColorNode(SimpleTreeNode node,String color){
            this.node = node;
            this.color = color;
        }
    }

    public List<Integer> inorderTraversal(SimpleTreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }

        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root,"white"));

        while(!stack.empty()){
            ColorNode cn = stack.pop();

            if(cn.color.equals("white")){
                if(cn.node.right != null) {
                    stack.push(new ColorNode(cn.node.right,"white"));
                }
                stack.push(new ColorNode(cn.node,"gray"));
                if(cn.node.left != null) {
                    stack.push(new ColorNode(cn.node.left,"white"));
                }
            }else{
                res.add(cn.node.val);
            }
        }

        return res;
    }
}
